package array

func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1

	for i := 2; i <= n; i++ {
		temp := 0
		for j := 0; j < i; j++ {
			temp += dp[j] * dp[i-j-1]
		}
		dp[i] = temp
	}
	return dp[n]
}
